package org.liaohailong.helloworld.hash;

import java.util.LinkedList;

/**
 * Author: liaohailong
 * Time: 2021/5/28 11:29
 * Describe:
 */
public class RandomizedSet {

    private static final int MAX_CAP = 1 << 30;

    private int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return n < 0 ? 1 : n >= MAX_CAP ? MAX_CAP : n + 1;
    }

    private int indexFor(int key) {
        return key & (table.length - 1);
    }

    private void resize() {
        if (size >= table.length * 0.75f) {
            int newLen = table.length << 1;
            Integer[] oldTable = table;
            table = new Integer[newLen];
            indexes.clear();
            for (Integer val : oldTable) {
                if (val != null) {
                    int i = indexFor(val);
                    table[i] = val;
                    indexes.add((Integer) i);
                }
            }
        }
    }

    private Integer[] table;
    private int size;
    private LinkedList<Integer> indexes = new LinkedList<>();

    /**
     * Initialize your data structure here.
     */
    public RandomizedSet() {
        int count = tableSizeFor(16);
        table = new Integer[count];
        size = 0;
    }

    /**
     * Inserts a value to the set. Returns true if the set did not already contain the specified element.
     */
    public boolean insert(int val) {
        int i = indexFor(val);
        boolean empty = table[i] == null;
        if (empty) {
            table[i] = val;
            size++;
            resize();
            indexes.add((Integer) i);
        }
        return empty;
    }

    /**
     * Removes a value from the set. Returns true if the set contained the specified element.
     */
    public boolean remove(int val) {
        int i = indexFor(val);
        boolean empty = table[i] == null;
        if (!empty) {
            table[i] = null;
            size--;
            indexes.remove((Integer) i);
        }
        return !empty;
    }

    private int random = -1;
    /**
     * Get a random element from the set.
     */
    public int getRandom() {
        random++;
        int i = random % indexes.size();
        Integer val = indexes.get(i);
        int index = indexFor(val);
        return table[index];
    }

}
